/*
 * Btree.h
 *
 *  Created on: Mar 28, 2011
 *      Author: hxu
 *      Btree<root, children>
 */

#ifndef BTREE_H_
#define BTREE_H_
#include "Network.h"
#include "BtreeNode.h"
#include <vector>
#include "Buffer.h"
#include "MergingSegment.h"

namespace Cxuh {

class Btree: public Network<int> {
	//tree structure, general list
public:
	Btree(int idd);
	virtual ~Btree();
	int getID() const;
	void setRoot(BtreeNode *elem); // link the head pointer to the root node
	bool isEmpty(); // whether the Btree is empty
	void setParent(BtreeNode *elem, BtreeNode *par); // set the parent of elem
	void addSink(BtreeNode* newsink); // add a sink
	void Add(Cxuh::Segment<int>*) {
	}

	BtreeNode* getRoot() {
		return root;
	}

	std::vector<Cxuh::BtreeNode*> getSinks() {
		return sinks;
	}

	void CTS3D(); // clock tree synthesis 3D
	void CTS(); // clock tree synthesis 2D
	BtreeNode* MMM(std::vector<Cxuh::BtreeNode*>& nodes); // top-down MMM 2D
	BtreeNode* MMM(std::vector<Cxuh::BtreeNode*>& nodes, char direction); // top-down MMM 2D
	BtreeNode* centerofset(const std::vector<BtreeNode*>& nodes); // return the among the nodes
	std::vector<Cxuh::BtreeNode*> subSet(const std::vector<Cxuh::BtreeNode*>&,
			BtreeNode*, char); // divide a set into two sets
	int d2subcenter(const std::vector<BtreeNode*>& nodes, char direction); // delay from center of nodes to the center of its subset, in the specified direction
	friend std::ostream& operator <<(std::ostream&, Btree&);
	void traverse(std::ostream&, BtreeNode*); // preorder traverse
	int getNumMP() {
		return num_mp;
	} // return # merge points
	BtreeNode* MMM3D(std::vector<Cxuh::BtreeNode*>& nodes, int TSVbound,
			char direction); // top-down MMM considering Z-cut
	BtreeNode* XYcut(const std::vector<Cxuh::BtreeNode*>& nodes,
			std::vector<Cxuh::BtreeNode*>& nodes1,
			std::vector<Cxuh::BtreeNode*>& nodes2, double& TSVratio,
			char direction); // XYcut for 3D nodes
	BtreeNode* Zcut(const std::vector<Cxuh::BtreeNode*>& nodes,
			std::vector<Cxuh::BtreeNode*>& nodes1,
			std::vector<Cxuh::BtreeNode*>& nodes2);
	void findzMinMax(const std::vector<Cxuh::BtreeNode*>& nodes, int& min1,
			int& max1); // find the min&max z of a set
	int minN(const std::vector<Cxuh::BtreeNode*>& nodes); // min nsink within the same tier in nodes
	void genTSV(BtreeNode* sroot, BtreeNode* sroot1); // generate a TSV between sroot and sroot1
	void replaceNode(BtreeNode* oldnd, BtreeNode* newnd); // replace oldnd with newnd
	void insertNode(BtreeNode* oldnd, BtreeNode* newnd); // insert newnd before oldnd
	int getNumTSV() {
		return num_tsv;
	}
	int getNumBuf() {
		return num_buf;
	}
	void buffering(BtreeNode* rt, double Cprev); // slew-aware buffer insertion for the entire tree, constraint is BUFLOAD
	void buffering(BtreeNode* rt); // slew-aware buffer insertion for the entire tree
	double getInload(BtreeNode* nd); // get the cap load seen at the input of nd
	void printPaths(std::ostream& out); // print all paths
	void findXYMinMax(int& xmin, int& xmax, int& ymin, int& ymax);	// get the boundary of sinks
	void display4sim(std::ostream& out, const int id1);		// display shared and independent segments for sim
	void DME3D();	// DME 3D including buffer insertion
	MergingSegment* DME3D_1(BtreeNode* nd);	// DME 3D 1st phase, bottom-up
	BtreeNode* DME3D_2(MergingSegment* ms);	// DME 3D 2nd phase, top-down
	void update(BtreeNode* rt);	// update the count and label in the subtree
	void update();	// update the count and labels of all nodes
	double get_pathd_min() const;
	double get_pathd_max() const;

	int counter;

	static int TSV_bound_per_tier;
	static int tier_of_src;
	static const double ELMORE_DISTR; // distributed Elmore coefficients
	static const double ELMORE_LUMP; // lumped Elmore coefficients

private:
	BtreeNode* root;
	int id; // id of the Btree
	std::vector<Cxuh::BtreeNode*> sinks; // only sinks
	int num_mp; // id of merge point
	int num_tsv; // # tsv
	int num_buf;
	int srcz; // z of clk src
	double pd_min, pd_max; // path delay min and max

	void deleteNode(BtreeNode* nd); // free memory
	void DME3D_simple(BtreeNode *rt, const bool insert_buf); // simplified version of DME3D, without merging segments
	double DME3D_simple(BtreeNode *rt, double& c, const bool insert_buf); // sub procedure of DME3D_simple(rt), get the load C and the largest delay from rt to the sinks
	double det_branch_between_nodes(BtreeNode *rt, double& ctotal, double dl, double Cl, double dr, double Cr);	// determine the length of branches between lchd and rchd, dl is the largest delay from lchd to sinks, Cl is the cap seen at lchd
	double det_branch_nobuf(BtreeNode *rt, double& Ctotal,
		BtreeNode *lchd, double dl, double Cl, BtreeNode *rchd, double dr,
		double Cr); // determine the length of branches between lchd and rchd, dl is the largest delay from lchd to sinks, Cl is the cap seen at lchd
};

}

#endif /* Btree_H_ */
